package gold.digger;

import gold.utils.InputUtil;
import gold.vo.TreeNode;

import java.util.Arrays;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC988 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {

        private String ans;

        public String smallestFromLeaf(TreeNode root) {
            dfs(root, new StringBuilder());
            return ans;
        }

        private void dfs(TreeNode root, StringBuilder cur) {
            cur.append((char) (root.val + 'a'));
            if (root.left == root.right) { // leaf node
                final String s = new StringBuilder(cur)
                        .reverse().toString();
                if (null == ans || s.compareTo(ans) < 0) // 按字典序进行比较, 更新答案
                    ans = s;
                return;
            }
            for (TreeNode child : Arrays.asList(root.left, root.right)) {
                if (null == child) continue;
                dfs(child, cur);
                cur.setLength(cur.length() - 1); // bactracking ...
            }
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC988 an = new LC988();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
